package com.example.demo.suanfa;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 排序算法
 */
public class OrderSort {


    /**
     * 二分查找
     */
    @Test
    public void exist(){
        int[] orderArray = generateOrderArray(100,100);
        int target = 10;
        int L = 0;
        int R = orderArray.length - 1;
        boolean flag = false;
        while(L < R){
            int mid = L + ((R - L) >> 1);
            if (orderArray[mid] == target) {
                flag = true;
                break;
            }else if (orderArray[mid] > target){
                R = mid - 1;
            }else {
                L = mid + 1;
            }
        }
        flag = flag ? true : orderArray[L] == target;
        System.out.println(flag);
    }

    /**
     * 生成顺序整形数组
      * @param size
     * @param maxValue
     * @return
     */
    public int[] generateOrderArray(int size,int maxValue){
        int[] arr = generateRandomArray(100, 100);
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
        return arr;
    }

    /**
     * 插入排序
     */
    @Test
    public void insertOrder(){
        int[] arr = generateRandomArray(100);
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
        Arrays.stream(arr).forEach(System.out::println);
    }



    /**
     * 冒泡排序
     */
    @Test
    public void paopaoOrder() throws Exception {
        int[] arr = generateRandomArray(100);
        for (int j = 0; j < arr.length-1; j++) {
            for (int i = 0; i < arr.length-1; i++) {
                if (arr[i] > arr[i + 1]) {
                    swapValue(arr, i, i + 1);
                }
            }
        }
        Arrays.stream(arr).forEach(System.out::println);
        vlidateSort(arr);
    }


    private void swapValue(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // i==j     报错
    private void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    /**
     * 选择排序 On方
     * 从小到大
     * @throws Exception
     */
    @Test
    public void selectedSortOrder() throws Exception {
        int size = 100;
        int[] arr = generateRandomArray(size);


        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[minIndex] > arr[j] ? j : minIndex;
//                if (arr[i] > arr[j]){
//                    swapValue(arr, i, j);
//                }
            }
            swapValue(arr, i, minIndex);
        }
        Arrays.stream(arr).forEach(System.out::println);
        System.out.println(arr.length);
        vlidateSort(arr);
    }

    private void vlidateSort(int[] arr) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]){
                    throw new Exception("排序失败");
                }
            }
        }

    }

    private int[] generateRandomArray(int size) {
        int[] ret = new int[size];
        Random random = new Random();
        for (int j = 0 ; j< size;j++){
//            int i = RandomGenerator.getDefault().nextInt(size);
            ret[j] = random.nextInt(size);
        }
        return ret;
    }

    public int[] generateRandomArray(int maxSize, int maxValue){
        // Math.random() 返回 [0,1)所有小数，等概率返回一个
        // Math.random() * N [0,N)所有小数，等概率返回一个
        // (int)Math.random() * N [0,N]所有整数，等概率返回一个
        int[] arr = new int[(int) ((maxSize +1) * Math.random())];// 长度随机
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)((maxValue +1) *Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }


}
